/* 1823. 找出游戏的获胜者 */
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
/* 模拟 + 队列 */
var findTheWinner = function (n, k) {
    const queue = new Array(n).fill(0).map((_, i) => i + 1)
    while (queue.length !== 1) {
        for (let i = 1; i < k; i++) {
            queue.push(queue.shift())
        }
        queue.shift()
    }
    return queue[0]
};
/* 
    约瑟夫环问题
    数学 + 递归 
    删除前   删除后
    1          ...
    ...        ...
    k - 2      n - 2
    k - 1      n - 1
    k          删除掉了
    k + 1      1 
    k + 2      2
    n          ...
*/
var findTheWinner = function (n, k) {
    if (n === 1) return 1
    /* 
        为什么 + 1
        因为被n取余之后的结果范围是 0 ~ n-1,题目要求是 1 ~ n 所以 如果是 n - 1 + 1 => n
        0 => 1
        
        
        为什么 - 1 因为这个点被删了，所以使后面所有数向前移动一位
    */
    return (findTheWinner(n - 1, k) + k - 1) % n + 1
}
/* 数学 + 迭代 */
var findTheWinner = function (n, k) {
    let winner = 1
    for (let i = 2; i <= n; i++) {
        winner = (k + winner - 1) % i + 1
    }
    return winner
}
findTheWinner(5, 2)